package com.example.algorithm.huawei_rongyao_29;

// 红包出现频率过半数的金额
// 难度：难。

/**
 * 要找到红包金额数组中出现次数超过总数一半的红包金额，可以利用 摩尔投票算法（Boyer-Moore Voting Algorithm）。
 * 注意，如果有多个相同频率的金额，摩尔算法，我实际测试发现，它就不管用了。它返回了0，表示找不到金额。如{1, 1, 2, 2, 2, 3, 3, 3}
 * 但是，我们分析题目可以得到一种隐含信息，就是，如果一个金额过半数，那么，即使剩下的金额都是同样的另外的一个金额，这个金额的次数也不可能和前面那个金额次数一样。
 * 所以，只要存在有过半数的金额，摩尔算法一定能找出那个金额。而如果该金额不过半数，那摩尔算法一定找不出，会返回0。真神奇啊。
 * 这个算法在一个线性时间复杂度 O(n) 和常量空间复杂度 O(1) 内解决这个问题，非常高效。
 *
 * 摩尔投票算法（Boyer-Moore Voting Algorithm）是一种用于在一个序列中找到占多数元素的算法。该算法的核心思想是通过两个步骤来确定占多数的元素：计数和验证。
 *
 * 算法步骤
 * 计数阶段：
 *
 * 设定一个候选人（candidate）和一个计数器（count），初始时候选人可以是任何元素，计数器设为0。
 * 遍历数组：
 * 如果计数器为0，将当前元素设为候选人，并将计数器设为1。
 * 如果当前元素与候选人相同，计数器加1。
 * 如果当前元素与候选人不同，计数器减1。
 * 验证阶段：
 *
 * 再次遍历数组，验证候选人是否确实为多数元素（出现次数超过数组长度的一半）。
 */
public class Q21_RedEnvelope {

    public static void main(String[] args) {
        //int[] gifts = {1, 2, 3, 2, 2, 2, 5, 2, 2};
        //int[] gifts = {1, 1, 2, 2, 2, 3, 3, 3};
        int[] gifts = {1, 2, 3, 3, 3, 7, 7, 7, 7};
        int n = gifts.length;
        System.out.println(getValue(gifts, n));  // Output: 2
    }

    public static int getValue(int[] gifts, int n) {
        int candidate = 0;
        int count = 0;

        // Step 1: Find the candidate using Boyer-Moore Voting Algorithm
        for (int i = 0; i < n; i++) {
            if (count == 0) { // for第一次，必然走这个。本例中第三次走这个。
                candidate = gifts[i]; // 找一个金额当候选人。其实就是第一个元素
                count = 1;
            } else if (gifts[i] == candidate) {
                count++;
            } else {
                count--; // 本例中第二次走这个。本例中第四次走这个
            }
        }

        // Step 2: Verify the candidate
        // 为什么要验证呢？是因为，摩尔算法它只能帮助你在一个集合中找到占多数的元素。但是这个占多数的元素，它的多数不一定就多过n/2
        count = 0;
        for (int i = 0; i < n; i++) {
            if (gifts[i] == candidate) {
                count++;
            }
        }
        if (count > n / 2) {
            return candidate;
        } else {
            return 0;
        }
    }
}

